#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>

#include "PriorityQueue.h"

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOREACH(i, coll) for (typeof(coll.begin()) i = coll.begin(); i != coll.end(); ++i)

template <typename Scalar>
Scalar abs(Scalar x) {
	return x >= 0 ? x : -x;
}

template <typename IndexType, typename ScalarType>
class SparseMatrix {

/*	class Compar {
		bool operator<(const std::pair<IndexType, IndexType>& lhs,
									 const std::pair<IndexType, IndexType>& rhs) const {
			return lhs.first < rhs.first;
		}
	};*/

public:
	vector<map<IndexType, ScalarType> > rows_;	
	vector<map<IndexType, ScalarType> > cols_;
	std::set<std::pair<IndexType, IndexType> > ones_;

	struct Coordinates {
		IndexType row, col;

		Coordinates(IndexType r, IndexType c) : row(r), col(c) {}

		bool operator<(const Coordinates& other) const {
			ScalarType a = abs(rows_[row][col]);
			ScalarType b = abs(rows_[other.row][other.col]);
			return a < b || a == b && rows_[row].size() < rows_[other.row].size();
		}
	};

	public:

	SparseMatrix(int row_count, int col_count) : rows_(row_count), cols_(col_count) {}

	ScalarType get(const IndexType& r, const IndexType& c) const {
		typename map<IndexType, ScalarType>::const_iterator col_iter = rows_[r].find(c);
		return (col_iter == rows_[r].end()) ? 0 : col_iter->second;	
	}

	map<IndexType, ScalarType> get_row(const IndexType& r) const {
		return rows_[r];
	}

	map<IndexType, ScalarType> get_col(const IndexType& c) const {
		return cols_[c];
	}

	int get_row_size(const IndexType& r) const {
		return rows_[r].size();
	}
	
	int get_col_size(const IndexType& c) const {
		return cols_[c].size();
	}

	void set(const IndexType& r, const IndexType& c, const ScalarType& value) {
		if (value == 0) {
			rows_[r].erase(c);
			cols_[c].erase(r);
		} else {
			rows_[r][c] = value; 
			cols_[c][r] = value;
		}
		if (abs(value) == 1)
			ones_.insert(std::make_pair(r, c));
		else
			ones_.erase(std::make_pair(r, c));
	}

	void delete_row(const IndexType& r) {
		map<IndexType, ScalarType> row = get_row(r);
		FOREACH(c_, row) 
			set(r, c_->first, 0);
	}

	void delete_col(const IndexType& c) {
		map<IndexType, ScalarType> col = get_col(c);
		FOREACH(r_, col) 
			set(r_->first, c, 0);
	}
	
	void sub_col(const IndexType& c1, const IndexType& c2, const ScalarType& a) {
		FOREACH(r_, cols_[c2]) { 
			const IndexType& r = r_->first;
			set(r, c1, cols_[c1][r] - a * cols_[c2][r]);
		}
	}

	bool find_any(IndexType* r, IndexType* c) {
		bool found = false;
		REP(r_, rows_.size())
			FOREACH(c_, rows_[r_]) 
				if (abs(c_->second) == 1) 
					if (!found || rows_[r_].size() < rows_[*r].size()) {
						*r = r_;
						*c = c_->first;
						found = true;
					}
		return found;	
	}

	bool find_min(IndexType* r, IndexType* c) {
		if (!ones_.size())
			return false;
		std::pair<IndexType, IndexType> coord = *ones_.begin();
		*r = coord.first;
		*c = coord.second;
		return true;
	}

	bool find_best(IndexType* r, IndexType* c) {
		
	}
};

